package Data_Structure.Sort;

/**
 * @className: BubbleSort
 * @author: 芃
 * @description: 冒泡排序实现
 * @date: 2023/8/20 17:17
 */
//主要思想：每趟将最大的（或最小的元素）沉到数组末尾
//共进行i-1趟，其中i为数组中的元素个数
//每趟只需要比较i-1-趟数 即可
//优化：当某一趟未发生交换时，就说明数组已经有序，排序完成

//时间复杂度：O（N^2）
//空间复杂度：O(1)
//稳定性：稳定的
public class BubbleSort {
    public static void bubbleSort(int[] arr){
        for (int i = 0; i < arr.length - 1; i++) {
            boolean flg = true;
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j+1]){
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                    flg =false;
                }
            }
            if (flg){//说明这一趟没有发生过交换，则已经有序
                break;
            }
        }
    }
}
